Home | | Latest | About | Random
# Week 5 Friday
Dear Class,
**Please read sections 10, 11, and 12.** Main ideas today:
- **Pass by value** vs **pass by reference**
- The `std::vector` class template.
- Reference to `const` (`const T&`)
- Why might one want to...
- pass by reference, or
- pass by reference to `const` for a function.
For your own reading, please go through **10.5** (references to `const`) and **section 11** (vectors) in the text (and check out the **snippet** in section 11 that details some vector operations!), and try the **review questions in 10.6 and 11.4**. Then, continue with **section 12**, on choosing parameter types.
Have a safe spooo00oOooooky weekend!
-- B.
.
.
.
.
.
## Warm-up on `&`: Follow the arrows! The arrow never change!
Remember from last time,
- `void my_swap(int a, int b)` gets **copies** of its arguments. This is **pass by value**. Changing `a` and `b` inside does nothing to the caller's variables.
- `void good_swap(int& a, int& b)` gets **references** to its arguments. This is **pass by reference**. The parameters are arrows to the caller's variables, so changing `a` and `b` changes them.
What does this print? Draw the function scope with its arrows to help you!
```cpp
#include
using namespace std;
void f(int& a, int b, int& c) {
a += 1;
b *= 10;
c *= 2;
cout << a << ' ' << b << ' ' << c << endl;
}
int main() {
int x = 1;
while (x < 10) {
f(x, x, x);
cout << x << endl;
}
return 0;
}
```
.
.
.
.
.
Note, when calling `f(x, x, x)`, the parameters are initialized with the arguments, in order: it is like `int& a = x;`, `int b = x;`, `int& c = x;`. So `a` and `c` are **passed by reference**, both arrows to `main`'s `x`, while `b` is **passed by value**, which has its own memory box inside the function scope holding a copy of the value of `x`.
And yes, two references can refer to the same storage location.
.
.
.
.
.
Output:
```
4 10 4
4
10 40 10
10
```
.
.
.
.
.
## `std::vector`. Many values in one variable.
**(More details in the book, section 11)**
Say we want to keep the scores of 200 students. Declaring `int score0, score1, ..., score199;` is not going to work!
A `vector` allows us to store many values of **one same type** in a row. (One can think of a `string` as a variable that allows us to store many `char`s in a row)
```cpp
#include
```
(And assuming we have `using namespace std;`)
```cpp
vector scores; // a vector of ints
vector prices; // a vector of doubles
vector names; // a vector of strings
```
The type in the angle brackets `< >` is the **element type**. We have seen angle brackets before, in `static_cast(x)`!
`vector` is a **class template**: `vector` by itself is not a type, it is a recipe for making types. Each of `vector`, `vector`, `vector` is its own class. Even `vector>` is a class: a vector whose elements are vectors of `int`s!
**Remark.** A vector can **grow and shrink** while the program runs. When it runs out of room, it moves its elements to a bigger block of memory. How exactly this works is a story for PIC 10B.
### Creating vectors.
```cpp
vector a; // empty, size 0
vector b(3); // 0 0 0
vector c(3, 7); // 7 7 7
vector d = {2, 4, 6}; // 2 4 6
vector e {3, 7}; // 3 7
vector f(2, "hi"); // "hi" "hi"
```
- `vector v(n);` makes `n` elements, each **value-initialized**. For `int` and `double` that means `0`, for `string` the empty string.
- `vector v(n, t);` makes `n` copies of `t`.
- `vector v = {...};` lists the elements one by one.
- `vector v {...};` does the same thing as `= {...}`.
**Careful!** `vector p(5);` is five zeros, but `vector q {5};` is one element, the number `5`. **Braces list the elements. Parentheses give a size (and a value).**
.
.
.
.
.
### Member functions of `vector`.
Many look just like the ones for `string`!
| Member function | What it does |
| ------------------ | --------------------------------------------------------------- |
| `v.size()` | the number of elements, a `size_t` |
| `v.empty()` | `true` if `v` has no elements |
| `v.at(i)`, `v[i]` | the `i`-th element |
| `v.push_back(t)` | adds `t` to the end |
| `v.pop_back()` | removes the last element |
| `v.clear()` | removes all elements |
| `v.resize(n)` | makes the size `n`, new elements are value-initialized |
| `v.resize(n, t)` | makes the size `n`, new elements are copies of `t` |
### Indexing, same rules as `string`.
```cpp
vector v = {10, 20, 30};
cout << v[0] << endl; // 10
v[0] = 15; // change an element
v.at(1) += 5; // v is now 15 25 30
v.push_back(40); // v is now 15 25 30 40
```
- Counting starts at `0`. The last element is `v[v.size() - 1]`.
- `v.at(i)` with `i >= v.size()` is a **runtime error**: the program stops with an error message.
- `v[i]` with `i >= v.size()` is **undefined behavior**: no checking at all!
### Looping over a vector.
Same as looping over a `string`, with a `size_t` index:
```cpp
vector v = {3, 1, 4, 1, 5};
int total = 0;
for (size_t i = 0; i < v.size(); ++i) {
total += v[i];
}
cout << total << endl; // 14
```
(For practice with `push_back`, `pop_back` and `resize`, try review question 1 in 11.4!)
.
.
.
.
.
## Printing a vector.
Can we just `cout << v;`? No! That is a **build error**. `cout` does not know how to print a vector. (Teaching `cout` to print a vector would require something called *overloading*) So let's write a function call `print`, passing the vector **by value**:
```cpp
/**
Prints the elements of a vector of ints, like { 3, 1, 4 }.
@param v : the vector to print
*/
void print(vector v) {
if (v.empty()) { // careful: v.size() - 1 would wrap around!
cout << "{ }" << endl;
return;
}
cout << "{ ";
for (size_t i = 0; i < v.size() - 1; ++i) {
cout << v[i] << ", ";
}
cout << v[v.size() - 1] << " }" << endl;
}
```
So `{3, 1, 4}` prints as `{ 3, 1, 4 }`.
.
.
.
.
.
### How many `int`s get copied?
```cpp
int main() {
vector w(10000, 8);
print(w);
print(w);
print(w);
return 0;
}
```
The parameter is `vector v`, so each call is like `vector v = w;`, a **copy**. How many `int`s get copied?
.
.
.
.
.
Each call copies all `10000` ints, so `30000` ints are copied, just to **look** at `w`! And then each copy is destroyed when the call ends.
We already know how to avoid a copy: **pass by reference!**
```cpp
void print(vector& v) { ... } // same body as before
```
Now each call is like `vector& v = w;`, just an arrow. **No copies at all.**
.
.
.
.
.
### A mystery.
```cpp
const vector primes = {2, 3, 5, 7};
print(primes); // BUILD ERROR!
```
**Huh??** All `print` does is look at the vector. Why can't we print a `const` vector? To answer this, we need to look closely at references and `const`.
.
.
.
.
.
## Reference to `const`.
```cpp
int i = 1; // An initialized int variable i, holding value 1
const int& r = i; // A reference to const
```
The type of `r` is `const int&`, read aloud "const int ref", a **reference to `const`**. It is still an arrow to `i`, but a **read-only** arrow: we can read `i` through `r`, but *not change* `i` through `r`.
```cpp
#include
using namespace std;
int main() {
int i = 1;
const int& r = i;
cout << i << ' ' << r << endl;
i = 5; // fine, i itself is not const
cout << i << ' ' << r << endl;
// r = 7; // BUILD ERROR: cannot change i through a read-only arrow
return 0;
}
```
Output:
```
1 1
5 5
```
`r` still **sees** every change to `i`, it just cannot **make** any.
.
.
.
.
.
### Which arrows are allowed?
Which lines give a build error? Comment them out, then what is the output?
```cpp
#include
using namespace std;
int main() {
int i = 1;
const int j = 2;
i = 11;
j = 22;
int& r = i;
const int& s = i;
r = 111;
s = -111;
int& t = j;
const int& u = j;
u = -1111;
int& p = r;
const int& q = r;
p = 11111;
q = -11111;
int& x = s;
const int& y = s;
y = -111111;
cout << i << ' ' << j;
return 0;
}
```
.
.
.
.
.
Answer and comments.
```cpp
#include
using namespace std;
int main() {
int i = 1;
const int j = 2;
i = 11;
// j = 22; // BUILD ERROR: j is const
int& r = i;
const int& s = i;
r = 111; // i is now 111
// s = -111; // BUILD ERROR: s is a read-only arrow
// int& t = j; // BUILD ERROR: would remove const from j
const int& u = j;
// u = -1111; // BUILD ERROR: u is a read-only arrow
int& p = r; // p is an arrow to i
const int& q = r; // q is a read-only arrow to i
p = 11111; // i is now 11111
// q = -11111; // BUILD ERROR: q is a read-only arrow
// int& x = s; // BUILD ERROR: would remove const from s
const int& y = s; // y is a read-only arrow to i
// y = -111111; // BUILD ERROR: y is a read-only arrow
cout << i << ' ' << j;
return 0;
}
```
Output:
```
11111 2
```
| | to `int i` | to `const int j` | to `int& r` | to `const int& s` |
| ------------ | ---------- | ---------------- | ----------- | ----------------- |
| `int&` | ok | **build error** | ok | **build error** |
| `const int&` | ok | ok | ok | ok |
Why is `int& t = j;` a build error? If it were allowed, `t = 1111;` would change `j`, a `const`, through the back door! C++ protects us from ourselves.
**Rule of thumb.** You can always **add** `const` (a read-only arrow to something changeable is fine), but you can never **remove** it.
**Remark. Arrows never point to arrows.** `p`, `q`, `y` all point straight at `i`, not at `r` or `s`. And `int& x = s;` is a build error even though `i` is changeable: the compiler only sees that `s` is read-only. **Once you are behind a read-only arrow, everything after it stays read-only.** (Try review question 3 in 10.6!)
Think of sharing a document: if a friend gives you **view-only** access, you cannot give someone else **edit** access to it!
.
.
.
.
.
## Back to `print`.
Now we can solve the mystery! `print(primes)` with the parameter `vector& v` is like
```cpp
vector& v = primes; // primes is const!
```
That is `int& t = j;` all over again: it would **remove** `const`. Build error!
The fix: make the parameter a **reference to `const`**.
```cpp
/**
Prints the elements of a vector of ints, like { 3, 1, 4 }.
@param v : the vector to print
*/
void print(const vector& v) {
// same body as before
}
```
- `print(w);` is like `const vector& v = w;`. A read-only arrow, **no copy**.
- `print(primes);` is like `const vector& v = primes;`. A reference to `const` may refer to a `const` vector. **Works!**
- **Bonus.** A typo like `v[i] = 0` inside `print` is now a **build error**, so `print` can never erase your data by accident. And anyone reading just the declaration `void print(const vector& v);` knows their vector is safe, without reading the body.
.
.
.
.
.
### Three ways to pass a vector.
Think of sharing a document with a friend:
| Parameter | Like sharing a document... | Copies? | Can change the caller's vector? |
| ---------------------- | ---------------------------- | ------- | ------------------------------- |
| `vector v` | giving them a photocopy | yes | no (only the copy) |
| `vector& v` | giving them edit access | no | yes |
| `const vector& v` | giving them view-only access | no | no |
---
More about these can be read in **section 12**.
Postscript.
## Weekend reading: things we didn't get to say in class.
### More on references (section 10).
- **A reference to `const` can refer to a plain value.** `int& r = 4;` is a build error, but `const int& r = 4;` is ok! C++ quietly makes a hidden storage location holding `4`, and points the read-only arrow at it. This is why `void f(const string& s)` can be called as `f("hello")` (see Remark 12.1.1). The full story needs *l-values* and *r-values*, a PIC 10B topic.
- **Read-only arrows stay read-only through function calls, too.** A call initializes the parameters, so inside `void show(const int& y)`, calling `void bump(int& x)` as `bump(y)` is a build error: it is like `int& x = y;`, removing `const`. The compiler checks `show` without knowing who calls it (maybe someone calls `show(j)` with a `const int j`!), and `show` promised not to change its argument.
- **`const` on a reference means "*I* can't change it through this arrow", not "*nobody* will change it."** Just like `r` saw every change to `i`, a `const vector&` parameter sees any change made to the caller's vector by someone else.
- **Review question 3 in 10.6** has a reference initialized from another reference. Follow the arrows!
- **Review question 2.3 in 10.6:** passing a `double` to an `int&` parameter is a build error. Why? (Hint: an `int&` must refer to an existing storage location of type `int`.)
- **Remark 10.2.2:** a reference is secretly a `const` pointer that is automatically followed. We meet pointers in section 17.
- **Why is `std::swap` better than our `good_swap`?** It works for any type (it is a *template*), and for big objects it *moves* instead of copying. PIC 10B and 10C.
### More on vectors (section 11, and the snippet).
- **There is no `+` for vectors.** `a + b` and `a += b` are build errors, unlike for `string`s. Try writing your own:
```cpp
/**
Appends the elements of b to the end of a.
@param a : the vector to append to
@param b : the vector whose elements are appended
*/
void append(vector& a, const vector& b);
```
Why is `a` passed by reference, and `b` by reference to `const`? **Challenge:** what goes wrong with `append(a, a)` if your loop condition is `i < b.size()`? How do you fix it?
- **`resize` can shrink, too.** `vector v = {3, 1, 4, 1}; v.resize(2);` leaves `3 1`.
- **More undefined behavior:** `v.pop_back()` on an empty vector, and `v[v.size()] = 7;`, which writes past the end instead of adding an element (use `push_back`!).
- **`reserve` is not `resize`.** A vector has a **size** (how many elements you have) and a **capacity** (how many it has room for). `v.reserve(n)` only changes the capacity, not the size. So `vector v; v.reserve(10); v[0] = 1;` is undefined behavior! Until you care about speed, `resize` is almost always the one you want. (See the snippet.)
- **A loop trap from the snippet:** `for (size_t i = 0; i < w.size(); ++i) { w.pop_back(); }` does **not** empty `w`. Why? Two fixes: save the size first, `for (size_t i = 0, N = w.size(); i < N; ++i)`, or use `while (!w.empty()) { w.pop_back(); }`.
- **Vectors of vectors**, like `vector>`, are useful to represent **tables** and **matrices**.
- **How does a vector grow?** When it runs out of capacity, it finds a bigger chunk of memory (on "the heap") and moves its elements there. PIC 10B.
- **Teaching `cout` to print a vector** means writing your own `operator<<`, called *operator overloading*. PIC 10B.
### Try it at home.
1. What should the parameter types be for `sum`, which returns the sum of the elements of a vector of `int`s, and `double_all`, which doubles every element of a vector of `int`s? Write a function comment for each, too!
2. **Review question 2 in 11.4:** how many `int`s get created when we `print` a vector of `2000` ints by value? By reference to `const`?
3. Which of these calls build, given `void f(int& x); void g(const int& x); void h(int x);`, `int i = 1;` and `const int ci = 2;`?
```cpp
f(i); f(ci); f(7);
g(i); g(ci); g(7);
h(i); h(ci); h(7);
```